package com.zofer.study.linkedlist;

/**
 * 判断链表是否存在环
 */
public class HasCycle {

    public static void main(String[] args) {
        ListNode listNode3 = new ListNode(4);
        ListNode listNode2 = new ListNode(3);
        listNode2.next = listNode3;
        ListNode listNode1 = new ListNode(2);
        listNode1.next = listNode2;
        ListNode listNode = new ListNode(1);
        listNode.next = listNode1;
        boolean hasCycle = hasCycle(listNode);
        System.out.println("链表是否存在环状:"+hasCycle);
    }

    public static boolean hasCycle(ListNode head){
        if (head == null){
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        //如果链表不存在环,长度是奇数,fast.next == null;如果链表是偶数,fast == null
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow){
                return true;
            }
        }

        return false;
    }

}
